Non-Realizable Minimal Vertex Triangulations of Surfaces: Showing Non-Realizability using Oriented Matroids and Satisfiability Solvers

摘要

We show that no minimal vertex triangulation of a closed, connected,orientable 2-manifold of genus 6 admits a polyhedral embedding in R^3. We alsoprovide examples of minimal vertex triangulations of closed, connected,orientable 2-manifolds of genus 5 that do not admit any polyhedral embeddings.We construct a new infinite family of non-realizable triangulations ofsurfaces. These results were achieved by transforming the problem of findingsuitable oriented matroids into a satisfiability problem. This method can beapplied to other geometric realizability problems, e.g. for face lattices ofpolytopes.